NEAREST_ND_INTERP

Overview

The NEAREST_ND_INTERP function performs nearest-neighbor interpolation for scattered data in N-dimensional space (where N > 1). Given a set of known data points with associated values, the function estimates values at new query points by assigning each query point the value of its closest known data point.

This implementation uses SciPy’s NearestNDInterpolator, which internally constructs a k-d tree data structure via scipy.spatial.cKDTree for efficient nearest-neighbor lookup. The k-d tree is a space-partitioning binary tree that recursively subdivides the data space along alternating axes, enabling queries in approximately O(\log n) time complexity for well-distributed data, compared to O(n) for brute-force search.

Nearest-neighbor interpolation is particularly useful when:

Data is irregularly spaced or scattered across multiple dimensions
Preserving original data values exactly at sample points is required (no smoothing)
A simple, fast interpolation method is preferred over smoother alternatives

The algorithm assigns the value f(\mathbf{x}_i) to a query point \mathbf{q} where \mathbf{x}_i is the data point minimizing the Euclidean distance:

\mathbf{x}_i = \underset{\mathbf{x} \in X}{\arg\min} \|\mathbf{q} - \mathbf{x}\|_2

Unlike linear or spline interpolation methods, nearest-neighbor interpolation produces a piecewise-constant surface with discontinuities at the boundaries between regions. For smoother results, consider LinearNDInterpolator or CloughTocher2DInterpolator. For data on regular grids, interpn provides a more efficient alternative.

This example function is provided as-is without any representation of accuracy.

Excel Usage

=NEAREST_ND_INTERP(points, values, xi)

points (list[list], required): Data point coordinates (n_points, n_dims)
values (list[list], required): Data values (n_points, 1)
xi (list[list], required): Query points (n_new_points, n_dims)

Returns (list[list]): A 2D list of interpolated values, or an error message (str) if invalid.

Examples

Example 1: Demo case 1

Inputs:

points		values	xi
0	0	0	0.1	0.1
1	0	1
0	1	1
1	1	2

Excel formula:

=NEAREST_ND_INTERP({0,0;1,0;0,1;1,1}, {0;1;1;2}, {0.1,0.1})

Expected output:

Result
0

Example 2: Demo case 2

Inputs:

points		values	xi
0	0	0	0.1	0.1
1	0	1	0.9	0.9
0	1	1
1	1	2

Excel formula:

=NEAREST_ND_INTERP({0,0;1,0;0,1;1,1}, {0;1;1;2}, {0.1,0.1;0.9,0.9})

Expected output:

Result
0
2

Example 3: Demo case 3

Inputs:

points			values	xi
0	0	0	10	0.2	0.1	0.1
1	0	0	20
0	1	0	30
0	0	1	40

Excel formula:

=NEAREST_ND_INTERP({0,0,0;1,0,0;0,1,0;0,0,1}, {10;20;30;40}, {0.2,0.1,0.1})

Expected output:

Result
10

Example 4: Demo case 4

Inputs:

points		values	xi
0	0	5	0.4	0.4
2	0	10	1.6	0.4
0	2	15	1.6	1.6
2	2	20

Excel formula:

=NEAREST_ND_INTERP({0,0;2,0;0,2;2,2}, {5;10;15;20}, {0.4,0.4;1.6,0.4;1.6,1.6})

Expected output:

Result
5
10
20

Python Code

import numpy as np
from scipy.interpolate import NearestNDInterpolator as scipy_NearestNDInterpolator

def nearest_nd_interp(points, values, xi):
    """
    Nearest neighbor interpolation in N > 1 dimensions.

    See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.NearestNDInterpolator.html

    This example function is provided as-is without any representation of accuracy.

    Args:
        points (list[list]): Data point coordinates (n_points, n_dims)
        values (list[list]): Data values (n_points, 1)
        xi (list[list]): Query points (n_new_points, n_dims)

    Returns:
        list[list]: A 2D list of interpolated values, or an error message (str) if invalid.
    """
    def to2d(x):
        return [[x]] if not isinstance(x, list) else x

    # Normalize inputs to 2D lists
    points = to2d(points)
    values = to2d(values)
    xi = to2d(xi)

    # Validate inputs are lists
    if not isinstance(points, list) or not isinstance(values, list) or not isinstance(xi, list):
        return "Invalid input: points, values, and xi must be 2D lists."

    # Validate all elements are lists
    if not all(isinstance(row, list) for row in points):
        return "Invalid input: points must be a 2D list."
    if not all(isinstance(row, list) for row in values):
        return "Invalid input: values must be a 2D list."
    if not all(isinstance(row, list) for row in xi):
        return "Invalid input: xi must be a 2D list."

    # Validate non-empty
    if len(points) == 0 or len(values) == 0 or len(xi) == 0:
        return "Invalid input: points, values, and xi must be non-empty."

    # Validate consistent dimensions
    if len(points) != len(values):
        return "Invalid input: points and values must have the same number of rows."

    # Validate all rows have same length
    n_dims = len(points[0])
    if n_dims == 0:
        return "Invalid input: points must have at least one column."
    if not all(len(row) == n_dims for row in points):
        return "Invalid input: all rows in points must have the same length."

    n_dims_xi = len(xi[0])
    if n_dims_xi == 0:
        return "Invalid input: xi must have at least one column."
    if not all(len(row) == n_dims_xi for row in xi):
        return "Invalid input: all rows in xi must have the same length."

    if n_dims != n_dims_xi:
        return "Invalid input: points and xi must have the same number of columns."

    # Validate values is single column
    if not all(len(row) == 1 for row in values):
        return "Invalid input: values must have exactly one column."

    # Convert to numpy arrays and validate numeric values
    try:
        points_arr = np.array(points, dtype=float)
        values_arr = np.array(values, dtype=float).flatten()
        xi_arr = np.array(xi, dtype=float)
    except (ValueError, TypeError):
        return "Invalid input: all elements must be numeric."

    # Check for NaN or inf values
    if np.any(np.isnan(points_arr)) or np.any(np.isinf(points_arr)):
        return "Invalid input: points contains non-finite values."
    if np.any(np.isnan(values_arr)) or np.any(np.isinf(values_arr)):
        return "Invalid input: values contains non-finite values."
    if np.any(np.isnan(xi_arr)) or np.any(np.isinf(xi_arr)):
        return "Invalid input: xi contains non-finite values."

    # Perform interpolation
    try:
        interp = scipy_NearestNDInterpolator(points_arr, values_arr)
        result = interp(xi_arr)
    except Exception as exc:
        return f"scipy.interpolate.NearestNDInterpolator error: {exc}"

    # Validate result
    if not isinstance(result, np.ndarray):
        return "scipy.interpolate.NearestNDInterpolator error: unexpected result type."

    # Check for NaN or inf in result
    if np.any(np.isnan(result)) or np.any(np.isinf(result)):
        return "scipy.interpolate.NearestNDInterpolator error: result contains non-finite values."

    # Convert to 2D list
    result_2d = [[float(val)] for val in result]

    return result_2d

Overview

Excel Usage

Examples

Python Code

Online Calculator